package main.Q1801_1900;

import java.util.Arrays;

public class Q1821_1830 {
    public static void main(String[] args) {
        System.out.println("Question1821：");
        System.out.println("Question1822：数组元素积的符号");
        System.out.println("Question1823：找出游戏的获胜者");
        System.out.println("Question1824：最少侧跳次数");
        System.out.println("Question1825：");
        System.out.println("Question1826：");
        System.out.println("Question1827：");
        System.out.println("Question1828：统计一个圆中点的数目");
        System.out.println("Question1829：每个查询的最大异或值");
        System.out.println("Question1830：");
    }
}

class Question1822 {
    public int arraySign(int[] nums) {
        int flag = 1;
        for (int num : nums) {
            if (num < 0) flag = -1 * flag;
            else if (num == 0) {
                flag = 0;
                break;
            }
        }
        return flag;
    }
}

class Question1823 {
    public int findTheWinner(int n, int k) {
        int result = 0;
        for (int i = 2; i <= n; i++) result = (result + k) % i;
        return result + 1;
    }
}

class Question1824 {
    public int minSideJumps(int[] obstacles) {
        int n = obstacles.length - 1;
        int[] dp = new int[3];
        Arrays.fill(dp, 1);
        dp[1] = 0;
        for (int i = 1; i <= n; i++) {
            int minCount = Integer.MAX_VALUE;
            for (int j = 0; j < 3; j++) {
                if (j == obstacles[i] - 1) {
                    dp[j] = Integer.MAX_VALUE;
                } else {
                    minCount = Math.min(minCount, dp[j]);
                }
            }
            for (int j = 0; j < 3; j++) {
                if (j == obstacles[i] - 1) {
                    continue;
                }
                dp[j] = Math.min(dp[j], minCount + 1);
            }
        }
        return Math.min(Math.min(dp[0], dp[1]), dp[2]);
    }
}

class Question1828 {
    public int[] countPoints(int[][] points, int[][] queries) {
        int m = points.length, n = queries.length;
        int[] result = new int[n];
        for (int i = 0; i < n; ++i) {
            int cx = queries[i][0], cy = queries[i][1], cr = queries[i][2];
            for (int j = 0; j < m; ++j) {
                int pointX = points[j][0], pointY = points[j][1];
                if ((cx - pointX) * (cx - pointX) + (cy - pointY) * (cy - pointY) <= cr * cr) {
                    ++result[i];
                }
            }
        }
        return result;
    }
}

class Question1829 {
    public int[] getMaximumXor(int[] nums, int maximumBit) {
        int[] result = new int[nums.length];
        int[] km = new int[maximumBit];//用于储存最大的k
        int now_xor = 0;
        for (int i = 0; i < nums.length; i++) {
            now_xor = now_xor ^ nums[i];
            int now_cp = now_xor;  //拷贝一下当前的异或后的值
            for (int j = 0; j < maximumBit; j++) {//计算k的每一位，即当now_xor中这位为1时，k 的这位为0 ，now_xor中这位为0时，k的这位为1
                if (now_cp != 0) {
                    int ni = now_cp & 1;
                    km[j] = ni == 0 ? 1 : 0;
                    now_cp >>= 1;
                } else {//当now_xor为0了，这时候剩下的肯定都是0了，直接将k补1即可
                    km[j] = 1;
                }
            }
            int temp = 0;
            for (int j = km.length - 1; j >= 0; j--) {//反向遍历km数组得到k的实际值，存入answer中即可
                temp += km[j];
                if (j != 0) temp <<= 1;
            }
            result[nums.length - 1 - i] = temp;
        }
        return result;
    }
}